372C - Watching Fireworks is Fun - CodeForces Solution

#include <iostream>
#include <queue>
#include <cmath>

using namespace std;

typedef long long int LL;

const LL N = 2e5, INF = 1e18;
LL dp[2][N], n;
deque <int> kol;

inline void push(int x) {
	if(kol.empty()) {
		kol.push_back(x);
		return;
	} while(!kol.empty() && dp[0][kol.back()] <= dp[0][x])
		kol.pop_back();
	kol.push_back(x);
}

inline void count_dp(int a, int b, LL dst) {
	for(int i = 0; i <= n; i++) {
		dp[0][i] = dp[1][i];
		dp[1][i] = -INF;
	} for(int i = 1; i < min(n + 1, dst); i++)
		push(i);
	for(int i = 1; i <= n; i++) {
		if(!kol.empty() && kol.front() < i - dst)
			kol.pop_front();
		if(i + dst <= n)
			push(i + dst);
		dp[1][i] = dp[0][kol.front()] + b - abs(a - i);
	} while(!kol.empty())
        kol.pop_back();
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	LL d, m, last = 0, ans = -INF; cin >> n >> m >> d;
	for(int i = 0; i < m; i++) {
		int a, b, t; cin >> a >> b >> t;
		count_dp(a, b, d * (t - last));
		last = t;
	} for(int i = 1; i <= n; i++)
		ans = max(ans, dp[1][i]);
	cout << ans << "\n";
	return 0;
}